Skip to main content

09. 그래프와 탐색(DFS, BFS:넓이우선탐색)

개념 정리​

그래프 (Graph)​

그래프는 정점과 간선으로 이루어진 자료구조이다.

정확히는 정점(Vertex)간의 관계를 표현하는 조직도이다. 그런면에서 트리는 그래프의 일종인 셈입니다. 다만 트리와는 달리 그래프는 정점마다 간선이 없을수도 있고 있을수도 있으며 루트 노드, 부모와 자식이라는 개념이 존재하지 않는다. ex) 지하철 노선도

특히 그래프를 순회하는 방식인 DFS와 BFS를 잘 알아두어야 한다.

넓이 우선탐색 BFS는 시작정점을 방문한 후 시작 정점에 인접한 모든 정점을 방문한 후 시작 정점에 인접한 모든 정점들을 우선 방문하는 방법이며 일반적으로 Queue를 사용해서 지금 위치에서 갈 수 있는 것들을 모두 큐에 넣는 방식으로 구현한다.

문제 풀이​

Ch.09 - 01. 그래프와 인접행렬​

const solution = () => {};

Ch.09 - 02. 경로탐색(DFS-인접행렬 : 노드개수가 적을 때)​

const solution = (n: number, multipleArr: Array<Array<number>>) => {
  let answer: number = 0;
  const graphArr: Array<Array<number>> = Array.from({ length: n + 1 }, () =>
    Array(n + 1).fill(0)
  );
  const checkArr = Array.from({ length: n + 1 }, () => 0);
  multipulArr.forEach(([x, y]) => (graphArr[x][y] = 1));

  (function DFS(v: number): void {
    if (v === n) answer++;
    else {
      for (let i = 2; i <= n; i++) {
        if (graphArr[v][i] === 1 && checkArr[i] === 0) {
          checkArr[i] = 1;
          DFS(i);
          checkArr[i] = 0;
        }
      }
    }
  })(1);

  return answer;
};

Ch.09 - 03. 경로탐색(DFS-인접리스트 : 노드개수가 많을 때 적용)​

const solution = (n: number, multipleArr: Array<Array<number>>): number => {
  let answer: number = 0;
  const graphArr: Array<Array<number>> = Array.from(
    { length: n + 1 },
    () => []
  );
  const checkArr: Array<number> = Array.from({ length: n + 1 }, () => 0);
  checkArr[1] = 1;

  multipleArr.forEach(([x, y]) => {
    graphArr[x].push(y);
  });

  (function DFS(v: number): void {
    if (v === n) answer++;
    else {
      for (let i = 0; i <= graphArr[v].length; i++) {
        if (checkArr[graphArr[v][i]] === 0) {
          checkArr[graphArr[v][i]] = 1;
          DFS(graphArr[v][i]);
          checkArr[graphArr[v][i]] = 0;
        }
      }
    }
  })(1);

  return answer;
};

Ch.09 - 04. 미로탐색​

const solution = (multipleArr: Array<Array<number>>): number => {
  let answer: number = 0;
  const n = multipleArr.length;

  multipleArr[0][0] = 1;

  const dx: Array<number> = [0, 1, 0, -1];
  const dy: Array<number> = [1, 0, -1, 0];

  (function DFS(x: number, y: number): void {
    if (x === n - 1 && y === n - 1) answer++;
    else {
      for (let i = 0; i < 4; i++) {
        const moveX: number = x + dx[i];
        const moveY: number = y + dy[i];

        if (
          0 <= moveX &&
          0 <= moveY &&
          moveX < n &&
          moveY < n &&
          multipleArr[moveX][moveY] === 0
        ) {
          multipleArr[moveX][moveY] = 1;
          DFS(moveX, moveY);
          multipleArr[moveX][moveY] = 0;
        }
      }
    }
  })(0, 0);

  return answer;
};

Ch.09 - 05. 이진트리 넓이우선탐색(BFS)​

const solution = () => {
  let answer: string = "";
  const queue: Array<number> = [1];
  while (queue.length) {
    const vertex = queue.shift();
    answer += `${vertex} `;
    for (const nv of [vertex * 2, vertex * 2 + 1]) {
      if (7 < nv) break;
      queue.push(nv);
    }
  }
  return answer;
};

Ch.09 - 06. 송아지 찾기(BFS)​

const solution = (myPoint: number, cowPoint: number): number => {
  let answer: number = 0;
  const checkArr: Array<number> = Array.from({ length: 10001 }, () => 0);

  const queue: Array<number> = [myPoint];
  while (queue.length) {
    const len: number = queue.length;

    for (let i = 0; i < len; i++) {
      const parnetVertex = queue.shift();
      for (const curVertex of [
        parnetVertex - 1,
        parnetVertex + 1,
        parnetVertex + 5,
      ]) {
        if (curVertex === cowPoint) return answer + 1;

        if (0 < curVertex && curVertex <= 10000 && checkArr[curVertex] === 0) {
          checkArr[curVertex] = 1;
          queue.push(curVertex);
        }
      }
    }
    answer++;
  }
};

Ch.09 - 07. 섬나라 아일랜드(DFS)​

const solution = (multipleArr: Array<Array<number>>): number => {
  let answer = 0;
  const n = multipleArr.length;

  const dx: Array<number> = [0, 1, 1, 1, 0, -1, -1, -1];
  const dy: Array<number> = [1, 1, 0, -1, -1, -1, 0, 1];

  function DFS(x: number, y: number): void {
    multipleArr[x][y] = 0;
    for (let k = 0; k < 8; k++) {
      const moveX = x + dx[k];
      const moveY = y + dy[k];

      if (
        0 <= moveX &&
        moveX < n &&
        0 <= moveY &&
        moveY < n &&
        multipleArr[moveX][moveY] === 1
      ) {
        DFS(moveX, moveY);
      }
    }
  }

  for (let i = 0; i < n; i++) {
    for (let j = 0; j < n; j++) {
      if (multipleArr[i][j] === 1) {
        answer++;
        DFS(i, j);
      }
    }
  }

  return answer;
};

Ch.09 - 07. 섬나라 아일랜드(BFS : 넓이우선탐색)​

const solution = (multipleArr: Array<Array<number>>): number => {
  let answer: number = 0;
  let n: number = multipleArr.length;

  const dx: Array<number> = [0, 1, 1, 1, 0, -1, -1, -1];
  const dy: Array<number> = [1, 1, 0, -1, -1, -1, 0, 1];

  const queue: Array<Array<number>> = [];
  for (let i = 0; i < n; i++) {
    for (let j = 0; j < n; j++) {
      if (multipleArr[i][j] === 1) {
        multipleArr[i][j] = 0;
        queue.push([i, j]);

        while (queue.length) {
          const [curX, curY] = queue.shift();
          for (let k = 0; k < 8; k++) {
            const moveX = curX - dx[k];
            const moveY = curY - dy[k];

            if (
              0 <= moveX &&
              moveX < n &&
              0 <= moveY &&
              moveY < n &&
              multipleArr[moveX][moveY] === 1
            ) {
              multipleArr[moveX][moveY] = 0;
              queue.push([moveX, moveY]);
            }
          }
        }
        answer++;
      }
    }
  }

  return answer;
};

참고​